/**
 * \file graph.c
 * \brief Implementação das funções sobre grafos (simples)
 */
# include "graph.h"

static int position (int a, int b) {
	int tmp;
	if (a < b) {
		tmp = a;
		a = b;
		b = tmp;
	}
	a = a*(a-1)/2;
	a += b;
	return a;
}

Graph * newGraph (int nodes) {
	Graph *g = (Graph *) malloc(sizeof(Graph));
	if (!g) logMessage("util.graphs","graph.c","newGraph","Memória Insuficiente (1)",CRITICAL);
	g->size = nodes*(nodes+1)/2;
	g->nodes = nodes;
	g->maxColors = 0;
	g->edge = (int *) malloc(sizeof(int)*g->size);
	if (!g->edge) logMessage("util.graphs","graph.c","newGraph","Memória Insuficiente (2)",CRITICAL);
	g->label = (int *) malloc(sizeof(int)*nodes);
	if (!g->label) logMessage("util.graphs","graph.c","newGraph","Memória Insuficiente (3)",CRITICAL);
	g->color = (int *) malloc(sizeof(int)*nodes);
	if (!g->color) logMessage("util.graphs","graph.c","newGraph","Memória Insuficiente (4)",CRITICAL);
	int i;
	for (i=0;i<nodes;i++) g->color[i] = 0;
	for (i=0;i<g->size;i++) g->edge[i] = DISCONNECTED;
	for (i=0;i<nodes;i++) g->label[i] = i;
	return g;
}

int adjacent (Graph *g, int vA, int vB) {
	if (vA == vB) 
		return DISCONNECTED;
	else
		return g->edge[position(vB,vA)];
}

void getVertices (int edge, int *vA, int *vB) {
	int tmp;
	float a;
	if (edge >= 0) {
		tmp = 1+(8*edge);
		a = (sqrtf(tmp) + 1)/2;
		*vA = (int) a;
		tmp = position(*vA,0);
		*vB = edge - tmp;
	}
}

int adjacentList (Graph *g, int vertice, int *result) {
	int i;
	int k=0;
	for (i=0;i<g->nodes;i++) {
		if (adjacent(g,i,vertice)) result[k++] = i;
	}
	return k;
}
static int validateEdge (Graph *g, int vA, int vB) {
	if (vA == vB) return ERROR;
	else if (vA >= g->nodes || vB >= g->nodes) return ERROR;
	else return SUCCESS;
}
int createEdge (Graph *g, int a, int b) {
	if (!validateEdge(g,a,b)) return ERROR;
	else g->edge[position(a,b)] = CONNECTED;
	return SUCCESS;
}

int setEdgeValue (Graph *g, int vA, int vB, int value) {
	if (!validateEdge(g,vA,vB)) return ERROR;
	else g->edge[position(vA,vB)] = value;
	return SUCCESS;
}

int getEdgeValue (Graph *g, int vA, int vB) {
	if (!validateEdge(g,vA,vB)) return -1;
	else return g->edge[position(vA,vB)];
}

static int haveNonChecked (int c[], int n) {
	int i;
	for (i=0;i<n;i++) if (!c[i]) return 1;
	return 0;
}
static int getFirstNonChecked (int c[], int n) {
	int i;
	for (i=0;i<n;i++) if (!c[i]) return i;
	return 0;
}
static int * getMem (int n) {
	int *m = (int *) malloc(sizeof(int));
	*m = n;
	return m;
}
static Graph * encurta (Graph *g, int *ver, int n) {
	int c = 0;
	int i,j;
	int map[g->nodes];
	Graph *new = newGraph(n);
	new->maxColors = g->maxColors;
	for (i=0;i<g->nodes;i++) {
		if (ver[i]) { map[i] = c; new->label[c++] = i; }
	}
	for (i=0;i<g->nodes;i++) {
		for (j=0;j<g->nodes;j++) {
			if (adjacent(g,i,j)) {
				createEdge(new,map[i],map[j]);
			}
		}	
	}
	if (c > n) printf("EERRRRO\n");
	freeGraph(g);
	return new;
}
static int getFirst (int *array,int n) {
	int i;
	for (i=0;i<n;i++) if (!array[i]) return i;
	return 0;
}
LinkedList * getConnectedSubGraphs (Graph *g) {
	LinkedList *lst = NULL;
	int mapped[g->nodes];
	int nMapped = 0;
	int i,start,it,*aux,n;
	Queue *q = newQueue();
	Graph *novo;
	it = 0;
	for (i=0;i<g->nodes;i++) mapped[i] = 0;
	start = 0;
	int verified[g->nodes], marked[g->nodes];
	while (nMapped < g->nodes) {
		novo = newGraph(g->nodes); n = 1;
		novo->maxColors = g->maxColors;
		for (i=0;i<g->nodes;i++) verified[i] = marked[i] = 0;
		start = getFirst(mapped,g->nodes);
		enqueue(q,getMem(start));
		nMapped++; mapped[start] = 1; marked[start] = 1;
		while (aux = dequeue(q)) {
			if (!verified[*aux]) {
				for (i=0;i<g->nodes;i++) {
					if (adjacent(g,*aux,i)) {
						if (!marked[i]) { marked[i] = 1; enqueue(q,getMem(i)); n++; }
						if (!mapped[i]) { mapped[i] = 1; nMapped++; }
						createEdge(novo,(int)*aux,i);
					}
				}
				verified[*aux] = 1;
			}
			free(aux);
		}
		lst = insertElemHead(lst,encurta(novo,verified,n));
	}
	return lst;
}

void freeGraph (Graph *g) {
	if (g) {
		if (g->edge) free(g->edge);
		if (g->label) free(g->label);
		if (g->color) free(g->color);
		free(g);
	}
}
